// 33题：搜索旋转排序树组 https://leetcode.cn/problems/search-in-rotated-sorted-array/


#include<vector>
#include<iostream>
#include<cassert>

using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.size() == 0) return -1;

        int left = 0, right = nums.size() - 1;

        while(left <= right){
            int mid = left + (right - left)/2;
            cout<<"mid, left, right: "<<mid<<","<<left<<","<<right<<endl;
            if(nums[mid] == target) return mid;
            if(nums[0] <= nums[mid]){
                // 左半边有序
                if (target >= nums[0] && target < nums[mid]){
                    // 目标在左半边范围中
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }else{
                // 右半边有序
                if(target > nums[mid] && target <= nums[right]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }

        return -1; // 不存在；
    }

    
};

int main(){
    cout<<"hello world"<<endl;
    Solution slu;
    // vector<int> input = {4,5,6,7,0,1,2};
    // int k = slu.search(input, 1);
    vector<int> input = {1,3,5};
    int k = slu.search(input,1);
    assert( k == 2);
    cout<<"k = "<<k<<endl;
    return 0;
}